package 剑指Offer.easy;

public class 青蛙跳台阶问题 {
    class Solution {
        public int numWays(int n) {
            int[] memo = new int[n + 1];
            return recursion(n, memo);
        }

        public int recursion(int n, int[] memo) {
            if (n == 0 || n == 1) {
                memo[n] = 1;
            }
            if (memo[n] > 0) {
                return memo[n];
            } else {
                memo[n] = (recursion(n - 1, memo) + recursion(n - 2, memo)) % 1000000007;
            }
            return memo[n];
        }
    }


}
